<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  <title>【状压dp练习】洛谷P1896 [SCOI2005]互不侵犯 P2704 [NOI2001]炮兵阵地.md | 蓝湖畔淅淅沥沥的雨</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="说明 - 2022-05-05 本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。 可以把一种只有两种状态的一维的数据组用一个整数表示，其二进制的值可以表示每一个位置的状态。如：101">
<meta property="og:type" content="article">
<meta property="og:title" content="【状压dp练习】洛谷P1896 [SCOI2005]互不侵犯 P2704 [NOI2001]炮兵阵地.md">
<meta property="og:url" content="http://example.com/1111/11/11/%E3%80%90%E7%8A%B6%E5%8E%8Bdp%E7%BB%83%E4%B9%A0%E3%80%91%E6%B4%9B%E8%B0%B7P1896%20[SCOI2005]%E4%BA%92%E4%B8%8D%E4%BE%B5%E7%8A%AF%20P2704%20[NOI2001]%E7%82%AE%E5%85%B5%E9%98%B5%E5%9C%B0/index.html">
<meta property="og:site_name" content="蓝湖畔淅淅沥沥的雨">
<meta property="og:description" content="说明 - 2022-05-05 本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。 可以把一种只有两种状态的一维的数据组用一个整数表示，其二进制的值可以表示每一个位置的状态。如：101">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="1111-11-11T03:06:11.000Z">
<meta property="article:modified_time" content="2022-05-06T07:35:52.497Z">
<meta property="article:author" content="StarsWhisper">
<meta property="article:tag" content="OldBlog(Before20220505)">
<meta property="article:tag" content="DP">
<meta name="twitter:card" content="summary">
  
    <link rel="alternate" href="/atom.xml" title="蓝湖畔淅淅沥沥的雨" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  
<link rel="stylesheet" href="/css/style.css">

  
<link rel="stylesheet" href="/plugin/bganimation/bg.css">

  

  <link href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.10.0/katex.min.css" rel="stylesheet" type="text/css">
<meta name="generator" content="Hexo 6.1.0"></head>

<body>
  <div id="container">
    <div id="wrap">
      <div class="outer">
        <div class="widget-wrap mobile-header">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <img class="avatar" src="/images/avatar.png">
    <h2 class="author">StarsWhisper</h2>
    <h3 class="description"></h3>
    <div class="count-box">
      <a href="/archives"><div><strong>75</strong><br>文章</div></a>
      <a href="/categories"><div><strong>31</strong><br>分类</div></a>
      <a href="/tags"><div><strong>56</strong><br>标签</div></a>
    </div>
    <ul class="blog-link">
     
          <a href="/" title="Home">
            <li>主页</li>
          </a>
        
          <a href="/archives" title="Archives">
            <li>归档</li>
          </a>
        
          <a href="/categories" title="Categories">
            <li>分类</li>
          </a>
        
          <a href="/tags" title="Tags">
            <li>标签</li>
          </a>
        
          <a href="/knightabout" title="Knightabout">
            <li>关于</li>
          </a>
        
          <a href="/bridges" title="Bridges">
            <li>传送门</li>
          </a>
        
          <a href="/announcement" title="Announcement">
            <li>公告</li>
          </a>
        
    </ul>
  </div>
</div>

        <section id="main"><article id="post-【状压dp练习】洛谷P1896 [SCOI2005]互不侵犯 P2704 [NOI2001]炮兵阵地" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E3%80%90%E7%8A%B6%E5%8E%8Bdp%E7%BB%83%E4%B9%A0%E3%80%91%E6%B4%9B%E8%B0%B7P1896%20%5BSCOI2005%5D%E4%BA%92%E4%B8%8D%E4%BE%B5%E7%8A%AF%20P2704%20%5BNOI2001%5D%E7%82%AE%E5%85%B5%E9%98%B5%E5%9C%B0/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      【状压dp练习】洛谷P1896 [SCOI2005]互不侵犯 P2704 [NOI2001]炮兵阵地.md
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/DP/">DP</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<p>可以把一种只有两种状态的一维的数据组用一个整数表示，其二进制的值可以表示每一个位置的状态。如：1010 表示第1、3个位置有，第2、4个位置没有。</p>
<h2 id="洛谷-p1896-scoi2005互不侵犯"><a class="markdownIt-Anchor" href="#洛谷-p1896-scoi2005互不侵犯"></a> 洛谷 P1896 [SCOI2005]互不侵犯</h2>
<p>init函数枚举所有的m位不存在两个相邻的1的整数，将整数的值记录在status数组中，将此数含有1的数量记录在cnt数组中<br />
dp[i][s][n] 表示进行道第i行时，在第s个状态，使用了n个国王的情况数。</p>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cmath&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdlib&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;map&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;set&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;stack&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="keyword">typedef</span> std::pair&lt;<span class="type">int</span> ,<span class="type">int</span>&gt; PP;</span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> LL;</span><br><span class="line"><span class="comment">//const int N = 1e5+5;</span></span><br><span class="line">LL dp[<span class="number">10</span>][<span class="number">1025</span>][<span class="number">100</span>];</span><br><span class="line"><span class="type">int</span> status[<span class="number">1025</span>],cnt[<span class="number">1025</span>];</span><br><span class="line"><span class="type">int</span> n,k;</span><br><span class="line"><span class="type">int</span> idx;</span><br><span class="line">LL ans;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">init</span><span class="params">(<span class="type">int</span> v,<span class="type">int</span> b,<span class="type">int</span> total)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">   <span class="keyword">if</span>(b &gt;=n)&#123;</span><br><span class="line">      status[idx] = v;</span><br><span class="line">      cnt[idx++] = total;</span><br><span class="line">      <span class="keyword">return</span> ;</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="built_in">init</span>(v,b+<span class="number">1</span>,total);</span><br><span class="line">   <span class="built_in">init</span>(v+(<span class="number">1</span>&lt;&lt;b),b+<span class="number">2</span>,total+<span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">   <span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>,&amp;n,&amp;k);</span><br><span class="line">   <span class="built_in">init</span>(<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>);</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;idx; i++)&#123;</span><br><span class="line">      dp[<span class="number">0</span>][i][cnt[i]] += <span class="number">1</span>;</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> r=<span class="number">1</span>; r&lt;n; r++)&#123;</span><br><span class="line">      <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;idx; i++)&#123;</span><br><span class="line">         <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>; j&lt;idx; j++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(status[i]&amp;status[j] || (status[i]&lt;&lt;<span class="number">1</span>)&amp;status[j] || (status[i]&gt;&gt;<span class="number">1</span>)&amp;status[j]) <span class="keyword">continue</span>;</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> x=cnt[i]; x&lt;=k; x++)&#123;</span><br><span class="line">               dp[r][i][x] += dp[r<span class="number">-1</span>][j][x-cnt[i]];</span><br><span class="line">            &#125;</span><br><span class="line">         &#125;</span><br><span class="line">      &#125;</span><br><span class="line">   &#125;</span><br><span class="line">   ans = <span class="number">0</span>;</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;idx; i++) ans += dp[n<span class="number">-1</span>][i][k];</span><br><span class="line">   <span class="built_in">printf</span>(<span class="string">&quot;%lld&quot;</span>,ans);</span><br><span class="line">   <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="p2704-noi2001炮兵阵地"><a class="markdownIt-Anchor" href="#p2704-noi2001炮兵阵地"></a> P2704 [NOI2001]炮兵阵地</h2>
<p>抄完了互不侵犯之后拿这道题练了练手，然后失败。</p>
<p><strong>写一个错误的思路</strong><br />
开 <strong>二维数组</strong> dp[i][s]表示进行到第i行时，当状态为s，可以摆放的最多的炮兵的数量。<br />
初始化前两行后，当一种状态s可以摆放，则dp[i][s] = max(自己，dp[i-2][上两行的状态]+上一行状态的总人数+这一行状态的总人数)<br />
<s>即用上到二行为止的最大人数+上一行某状态的人数+这一行s状态的人数来更新这一行的s状态</s><br />
这种思路存在一个缺陷，即只记录了单行某个状态的最大人数。<br />
沿用这个思路，当进行到第n行时，我们用“截止到n-2行k状态的最大人数”+“n-1行取状态j的人数”+“第n行状态s的人数”来更新第n行。 <strong>问题在于</strong><br />
：我们无法保证当“截止到n-2行k状态的最大人数”取得时，用状态j当作n-2行的下一行时合法的，因为第n-1行的状态受到n-2行和n-3行限制，有可能当“截止到n-2行k状态的最大人数”取得时，j状态是不能与n-3行的状态共存的。然而在这种思路中，我们下意识地认为这种错误时合法的，所以在多数情况下无法得到正确答案。<br />
<strong>更正思路：</strong><br />
开三维数组dp[i][s][last]，表示进行到第i行时，当状态为s，并且上一行状态为last时，可以摆放的最多的炮兵的数量。<br />
<strong>错误代码：</strong> (竟然还能得20分)</p>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cmath&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdlib&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;map&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;set&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;stack&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="comment">//typedef std::pair&lt;int ,int&gt; PP;</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> LL;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> N = <span class="number">105</span>,M = <span class="number">12</span>,ER9 = <span class="number">1030</span>;</span><br><span class="line"><span class="type">int</span> rows[N],status[ER9],va[ER9];</span><br><span class="line">LL dp[N][ER9];</span><br><span class="line"><span class="type">char</span> ss[<span class="number">12</span>];</span><br><span class="line"><span class="type">int</span> n,m;</span><br><span class="line"><span class="type">int</span> idx;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> id[N],mp[N][ER9];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">toStatus</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">   <span class="type">int</span> re = <span class="number">0</span>;</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;m; i++)&#123;</span><br><span class="line">      re += (ss[i] == <span class="string">&#x27;H&#x27;</span>) ? (<span class="number">1</span>&lt;&lt;i) : <span class="number">0</span>;</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="keyword">return</span> re;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">init</span><span class="params">(<span class="type">int</span> val,<span class="type">int</span> pos,<span class="type">int</span> cnt1)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">   <span class="keyword">if</span>(pos &gt;= m)&#123;</span><br><span class="line">      status[idx] = val;</span><br><span class="line">      va[idx++] = cnt1;</span><br><span class="line">      <span class="keyword">return</span> ;</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="built_in">init</span>(val,pos+<span class="number">1</span>,cnt1);</span><br><span class="line">   <span class="built_in">init</span>(val+(<span class="number">1</span>&lt;&lt;pos),pos+<span class="number">3</span>,cnt1+<span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">   <span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>,&amp;n,&amp;m);</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;n; i++)&#123;</span><br><span class="line">      <span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>,ss);</span><br><span class="line">      rows[i] = <span class="built_in">toStatus</span>();</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="built_in">init</span>(<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>);</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;idx; i++)&#123;</span><br><span class="line">      <span class="keyword">if</span>(status[i]&amp;rows[<span class="number">0</span>]) <span class="keyword">continue</span>;</span><br><span class="line">      mp[<span class="number">0</span>][id[<span class="number">0</span>]] = i;</span><br><span class="line">      dp[<span class="number">0</span>][id[<span class="number">0</span>]] = va[i];</span><br><span class="line">      id[<span class="number">0</span>] += <span class="number">1</span>;</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;idx; i++)&#123;</span><br><span class="line">      <span class="keyword">if</span>(status[i]&amp;rows[<span class="number">1</span>]) <span class="keyword">continue</span>;</span><br><span class="line">      mp[<span class="number">1</span>][id[<span class="number">1</span>]] = i;</span><br><span class="line">      <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>; j&lt;id[<span class="number">0</span>]; j++)&#123;</span><br><span class="line">         <span class="keyword">if</span>(status[i]&amp;status[mp[<span class="number">0</span>][j]]) <span class="keyword">continue</span>;</span><br><span class="line">         dp[<span class="number">1</span>][id[<span class="number">1</span>]] = std::<span class="built_in">max</span>(dp[<span class="number">1</span>][id[<span class="number">1</span>]],va[i]+dp[<span class="number">0</span>][j]);</span><br><span class="line">      &#125;</span><br><span class="line">      id[<span class="number">1</span>] += <span class="number">1</span>;</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> r=<span class="number">2</span>; r&lt;n; r++)&#123;</span><br><span class="line">      <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;idx; i++)&#123;</span><br><span class="line">         <span class="keyword">if</span>(status[i]&amp;rows[r]) <span class="keyword">continue</span>;</span><br><span class="line">         mp[r][id[r]] = i;</span><br><span class="line">         <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>; j&lt;id[r<span class="number">-1</span>]; j++)&#123;</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> k=<span class="number">0</span>; k&lt;id[r<span class="number">-2</span>]; k++)&#123;</span><br><span class="line">               <span class="keyword">if</span>(status[i]&amp;status[mp[r<span class="number">-1</span>][j]] || status[i]&amp;status[mp[r<span class="number">-2</span>][k]] || status[mp[r<span class="number">-2</span>][k]]&amp;status[mp[r<span class="number">-1</span>][j]]) <span class="keyword">continue</span>;</span><br><span class="line">               dp[r][id[r]] = std::<span class="built_in">max</span>(dp[r][id[r]],va[i]+va[mp[r<span class="number">-1</span>][j]]+dp[r<span class="number">-2</span>][k]);</span><br><span class="line">            &#125;</span><br><span class="line">         &#125;</span><br><span class="line">         id[r] += <span class="number">1</span>;</span><br><span class="line">      &#125;</span><br><span class="line">   &#125;</span><br><span class="line">   LL ans = <span class="number">0</span>;</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;id[n<span class="number">-1</span>]; i++)&#123;</span><br><span class="line">      ans = std::<span class="built_in">max</span>(ans,dp[n<span class="number">-1</span>][i]);</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="built_in">printf</span>(<span class="string">&quot;%lld&quot;</span>,ans);</span><br><span class="line"></span><br><span class="line">   <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>​</p>
<p><strong>AC代码:</strong><br />
看很多题解都说要用到三行的滚动数组，否则会MLE。<br />
但是这个没有用,直接开了100行，可能是由于动态加状态节省了空间吧。 <s>破案了，题目改过，不限制空间了</s></p>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cmath&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdlib&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;map&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;set&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;stack&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="comment">//typedef std::pair&lt;int ,int&gt; PP;</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> LL;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> N = <span class="number">105</span>,M = <span class="number">12</span>,E10 = <span class="number">1024</span>;</span><br><span class="line"><span class="type">int</span> rows[N],status[E10],va[E10],dp[N][E10][E10];</span><br><span class="line"><span class="comment">//rows:把地图的每一行转化为数字，H为1，P为0，储存在rows数组</span></span><br><span class="line"><span class="comment">//status记录所有状态的对应的数字</span></span><br><span class="line"><span class="comment">//va记录所有状态对应的人数</span></span><br><span class="line"><span class="comment">//dp[i][j][k]表示第i行状态为j，且i-1行状态为k时，可以放置的最大炮兵数</span></span><br><span class="line"><span class="type">char</span> ss[<span class="number">12</span>];</span><br><span class="line"><span class="type">int</span> n,m;</span><br><span class="line"><span class="type">int</span> idx,ans;</span><br><span class="line"><span class="comment">//idx记录status数组的大小</span></span><br><span class="line"><span class="type">int</span> id[N],mp[N][E10];</span><br><span class="line"><span class="comment">//id[i]数组记录第i行可行的总状态数</span></span><br><span class="line"><span class="comment">//mp[i][j]记录第i行第j个状态在status数组中对应的编号</span></span><br></pre></td></tr></table></figure>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">int</span> <span class="title">toStatus</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">   <span class="type">int</span> re = <span class="number">0</span>;</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;m; i++)&#123;</span><br><span class="line">      re += (ss[i] == <span class="string">&#x27;H&#x27;</span>) ? (<span class="number">1</span>&lt;&lt;i) : <span class="number">0</span>;</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="keyword">return</span> re;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">init</span><span class="params">(<span class="type">int</span> val,<span class="type">int</span> pos,<span class="type">int</span> cnt1)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">   <span class="keyword">if</span>(pos &gt;= m)&#123;</span><br><span class="line">      status[idx] = val;</span><br><span class="line">      va[idx++] = cnt1;</span><br><span class="line">      <span class="keyword">return</span> ;</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="built_in">init</span>(val,pos+<span class="number">1</span>,cnt1);</span><br><span class="line">   <span class="built_in">init</span>(val+(<span class="number">1</span>&lt;&lt;pos),pos+<span class="number">3</span>,cnt1+<span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">   <span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>,&amp;n,&amp;m);</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;n; i++)&#123;</span><br><span class="line">      <span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>,ss);</span><br><span class="line">      rows[i] = <span class="built_in">toStatus</span>();</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="built_in">init</span>(<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>);</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;idx; i++)&#123;</span><br><span class="line">      <span class="keyword">if</span>(status[i]&amp;rows[<span class="number">0</span>]) <span class="keyword">continue</span>;</span><br><span class="line">      mp[<span class="number">0</span>][id[<span class="number">0</span>]] = i;</span><br><span class="line">      dp[<span class="number">0</span>][id[<span class="number">0</span>]][<span class="number">0</span>] = va[i];</span><br><span class="line">      id[<span class="number">0</span>] += <span class="number">1</span>;</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;idx; i++)&#123;</span><br><span class="line">      <span class="keyword">if</span>(status[i]&amp;rows[<span class="number">1</span>]) <span class="keyword">continue</span>;</span><br><span class="line">      mp[<span class="number">1</span>][id[<span class="number">1</span>]] = i;</span><br><span class="line">      <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>; j&lt;id[<span class="number">0</span>]; j++)&#123;</span><br><span class="line">         <span class="keyword">if</span>(status[i]&amp;status[mp[<span class="number">0</span>][j]]) <span class="keyword">continue</span>;</span><br><span class="line">         dp[<span class="number">1</span>][id[<span class="number">1</span>]][j] = va[i] + dp[<span class="number">0</span>][j][<span class="number">0</span>];</span><br><span class="line">      &#125;</span><br><span class="line">      id[<span class="number">1</span>] += <span class="number">1</span>;</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> r=<span class="number">2</span>; r&lt;n; r++)&#123;</span><br><span class="line">      <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;idx; i++)&#123;</span><br><span class="line">         <span class="keyword">if</span>(status[i]&amp;rows[r]) <span class="keyword">continue</span>;</span><br><span class="line">         mp[r][id[r]] = i;</span><br><span class="line">         <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>; j&lt;id[r<span class="number">-1</span>]; j++)&#123;</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> k=<span class="number">0</span>; k&lt;id[r<span class="number">-2</span>]; k++)&#123;</span><br><span class="line">               <span class="keyword">if</span>(status[i]&amp;status[mp[r<span class="number">-1</span>][j]] || status[i]&amp;status[mp[r<span class="number">-2</span>][k]] || status[mp[r<span class="number">-2</span>][k]]&amp;status[mp[r<span class="number">-1</span>][j]]) <span class="keyword">continue</span>;</span><br><span class="line">               dp[r][id[r]][j] = std::<span class="built_in">max</span>(dp[r][id[r]][j],va[i]+dp[r<span class="number">-1</span>][j][k]);</span><br><span class="line">            &#125;</span><br><span class="line">         &#125;</span><br><span class="line">         id[r] += <span class="number">1</span>;</span><br><span class="line">      &#125;</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;id[n<span class="number">-1</span>]; i++) <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>; j&lt;id[n<span class="number">-2</span>]; j++)&#123;</span><br><span class="line">      ans = std::<span class="built_in">max</span>(dp[n<span class="number">-1</span>][i][j],ans);</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="built_in">printf</span>(<span class="string">&quot;%d&quot;</span>,ans);</span><br><span class="line">   <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>​</p>
<p>换了一波滚动数组，但是还是有10.+MB</p>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cmath&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdlib&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;map&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;set&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;stack&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="comment">//typedef std::pair&lt;int ,int&gt; PP;</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> LL;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> N = <span class="number">105</span>,M = <span class="number">12</span>,E10 = <span class="number">1024</span>;</span><br><span class="line"><span class="type">int</span> rows[N],status[E10],va[E10],dp[<span class="number">3</span>][E10][E10];</span><br><span class="line"><span class="comment">//rows:把地图的每一行转化为数字，H为1，P为0，储存在rows数组</span></span><br><span class="line"><span class="comment">//status记录所有状态的对应的数字</span></span><br><span class="line"><span class="comment">//va记录所有状态对应的人数</span></span><br><span class="line"><span class="comment">//dp[i][j][k]表示第i行状态为j，且i-1行状态为k时，可以放置的最大炮兵数</span></span><br><span class="line"><span class="type">char</span> ss[<span class="number">12</span>];</span><br><span class="line"><span class="type">int</span> n,m;</span><br><span class="line"><span class="type">int</span> idx,ans;</span><br><span class="line"><span class="comment">//idx记录status数组的大小</span></span><br><span class="line"><span class="type">int</span> id[<span class="number">3</span>],mp[<span class="number">3</span>][E10];</span><br><span class="line"><span class="comment">//id[i]数组记录第i行可行的总状态数</span></span><br><span class="line"><span class="comment">//mp[i][j]记录第i行第j个状态在status数组中对应的编号</span></span><br></pre></td></tr></table></figure>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">int</span> <span class="title">toStatus</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">   <span class="type">int</span> re = <span class="number">0</span>;</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;m; i++)&#123;</span><br><span class="line">      re += (ss[i] == <span class="string">&#x27;H&#x27;</span>) ? (<span class="number">1</span>&lt;&lt;i) : <span class="number">0</span>;</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="keyword">return</span> re;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">init</span><span class="params">(<span class="type">int</span> val,<span class="type">int</span> pos,<span class="type">int</span> cnt1)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">   <span class="keyword">if</span>(pos &gt;= m)&#123;</span><br><span class="line">      status[idx] = val;</span><br><span class="line">      va[idx++] = cnt1;</span><br><span class="line">      <span class="keyword">return</span> ;</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="built_in">init</span>(val,pos+<span class="number">1</span>,cnt1);</span><br><span class="line">   <span class="built_in">init</span>(val+(<span class="number">1</span>&lt;&lt;pos),pos+<span class="number">3</span>,cnt1+<span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">   <span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>,&amp;n,&amp;m);</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;n; i++)&#123;</span><br><span class="line">      <span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>,ss);</span><br><span class="line">      rows[i] = <span class="built_in">toStatus</span>();</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="built_in">init</span>(<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>);</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;idx; i++)&#123;</span><br><span class="line">      <span class="keyword">if</span>(status[i]&amp;rows[<span class="number">0</span>]) <span class="keyword">continue</span>;</span><br><span class="line">      mp[<span class="number">0</span>][id[<span class="number">0</span>]] = i;</span><br><span class="line">      dp[<span class="number">0</span>][id[<span class="number">0</span>]][<span class="number">0</span>] = va[i];</span><br><span class="line">      id[<span class="number">0</span>] += <span class="number">1</span>;</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;idx; i++)&#123;</span><br><span class="line">      <span class="keyword">if</span>(status[i]&amp;rows[<span class="number">1</span>]) <span class="keyword">continue</span>;</span><br><span class="line">      mp[<span class="number">1</span>][id[<span class="number">1</span>]] = i;</span><br><span class="line">      <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>; j&lt;id[<span class="number">0</span>]; j++)&#123;</span><br><span class="line">         <span class="keyword">if</span>(status[i]&amp;status[mp[<span class="number">0</span>][j]]) <span class="keyword">continue</span>;</span><br><span class="line">         dp[<span class="number">1</span>][id[<span class="number">1</span>]][j] = va[i] + dp[<span class="number">0</span>][j][<span class="number">0</span>];</span><br><span class="line">      &#125;</span><br><span class="line">      id[<span class="number">1</span>] += <span class="number">1</span>;</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> r=<span class="number">2</span>; r&lt;n; r++)&#123;</span><br><span class="line">      <span class="type">int</span> rm3 = r%<span class="number">3</span>,rs1m3 = (r<span class="number">-1</span>)%<span class="number">3</span>, rs2m3 = (r<span class="number">-2</span>)%<span class="number">3</span>;</span><br><span class="line">      <span class="built_in">memset</span>(dp[rm3],<span class="number">0</span>,<span class="built_in">sizeof</span>(rm3));</span><br><span class="line">      id[rm3] = <span class="number">0</span>;</span><br><span class="line">      <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;idx; i++)&#123;</span><br><span class="line">         <span class="keyword">if</span>(status[i]&amp;rows[r]) <span class="keyword">continue</span>;</span><br><span class="line">         mp[rm3][id[rm3]] = i;</span><br><span class="line">         <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>; j&lt;id[rs1m3]; j++)&#123;</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> k=<span class="number">0</span>; k&lt;id[rs2m3]; k++)&#123;</span><br><span class="line">               <span class="keyword">if</span>(status[i]&amp;status[mp[rs1m3][j]] || status[i]&amp;status[mp[rs2m3][k]] || status[mp[rs2m3][k]]&amp;status[mp[rs1m3][j]]) <span class="keyword">continue</span>;</span><br><span class="line">               dp[rm3][id[rm3]][j] = std::<span class="built_in">max</span>(dp[rm3][id[rm3]][j],va[i]+dp[rs1m3][j][k]);</span><br><span class="line">            &#125;</span><br><span class="line">         &#125;</span><br><span class="line">         id[rm3] += <span class="number">1</span>;</span><br><span class="line">      &#125;</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="type">int</span> ns1m3 = (n<span class="number">-1</span>)%<span class="number">3</span>, ns2m3 = (n<span class="number">-2</span>)%<span class="number">3</span>;</span><br><span class="line">   <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;id[ns1m3]; i++) <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>; j&lt;id[ns2m3]; j++)&#123;</span><br><span class="line">      ans = std::<span class="built_in">max</span>(dp[ns1m3][i][j],ans);</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="built_in">printf</span>(<span class="string">&quot;%d&quot;</span>,ans);</span><br><span class="line">   <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>​</p>
<h2 id="2020icpc-江西省大学生程序设计竞赛l-wzbs-harem"><a class="markdownIt-Anchor" href="#2020icpc-江西省大学生程序设计竞赛l-wzbs-harem"></a> 2020ICPC 江西省大学生程序设计竞赛L WZB’s Harem</h2>
<p><a target="_blank" rel="noopener" href="https://ac.nowcoder.com/acm/contest/15806/L">题目链接https://ac.nowcoder.com/acm/contest/15806/L</a><br />
题目翻译： n皇后问题的退化版——n车问题 n&lt;=20<br />
状压 yyds</p>
<p>​</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdlib&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cmath&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;string&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;stack&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;map&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;set&gt;</span></span></span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> <span class="type">int</span> LL;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> INF = <span class="number">0x7fffffff</span>, SCF = <span class="number">0x3fffffff</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> N = <span class="number">21</span>, MOD =  <span class="number">1000000007</span>;</span><br><span class="line"><span class="type">int</span> status[N][<span class="number">1</span>&lt;&lt;N],dp[N][<span class="number">1</span>&lt;&lt;N];</span><br><span class="line"><span class="type">int</span> id[N];</span><br><span class="line"><span class="type">int</span> board[N];</span><br><span class="line"><span class="type">int</span> qu[N];</span><br><span class="line"><span class="type">int</span> n;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">toStatus</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> re = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>; i&lt;=n; i++)&#123;</span><br><span class="line">        re = (re&lt;&lt;<span class="number">1</span>)+qu[i];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> re;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;n);</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>; i&lt;=n; i++)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">1</span>; j&lt;=n; j++)&#123;</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;qu[j]);</span><br><span class="line">        &#125;</span><br><span class="line">        board[i] = <span class="built_in">toStatus</span>();</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;(<span class="number">1</span>&lt;&lt;n); i++)&#123;</span><br><span class="line">        <span class="type">int</span> tt = i, cnt = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">while</span>(tt &gt; <span class="number">0</span>)&#123;</span><br><span class="line">            cnt += (tt&amp;<span class="number">1</span>);</span><br><span class="line">            tt &gt;&gt;= <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        status[cnt][id[cnt]++] = i;</span><br><span class="line">    &#125;</span><br><span class="line">    dp[<span class="number">0</span>][<span class="number">0</span>] = <span class="number">1</span>; <span class="comment">//No.Status 0, id 0;</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>; i&lt;=n; i++)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> k=<span class="number">0</span>; k&lt;id[i<span class="number">-1</span>]; k++)&#123;</span><br><span class="line">            <span class="type">int</span> pre = status[i<span class="number">-1</span>][k];</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>; j&lt;n; j++)&#123;</span><br><span class="line">                <span class="keyword">if</span>((pre&gt;&gt;j)&amp;<span class="number">1</span>) <span class="keyword">continue</span>;</span><br><span class="line">                <span class="keyword">if</span>( !( (<span class="number">1</span>&lt;&lt;j) &amp; board[i]) ) &#123;</span><br><span class="line">                    <span class="type">int</span> nxt = pre | (<span class="number">1</span>&lt;&lt;j);</span><br><span class="line">                    dp[i][nxt] = (dp[i][nxt] + dp[i<span class="number">-1</span>][pre]) % MOD;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    LL ans = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">2</span>; i&lt;=n; i++)&#123;</span><br><span class="line">        ans = ans*i%MOD;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;%lld&quot;</span>,ans * dp[n][(<span class="number">1</span>&lt;&lt;n)<span class="number">-1</span>] % MOD);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E3%80%90%E7%8A%B6%E5%8E%8Bdp%E7%BB%83%E4%B9%A0%E3%80%91%E6%B4%9B%E8%B0%B7P1896%20[SCOI2005]%E4%BA%92%E4%B8%8D%E4%BE%B5%E7%8A%AF%20P2704%20[NOI2001]%E7%82%AE%E5%85%B5%E9%98%B5%E5%9C%B0/" data-id="cl2uhoed60044e4j3alu42gnz" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/DP/" rel="tag">DP</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li></ul>

    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/1111/11/11/%E3%80%90%E7%8A%B6%E5%8E%8BDP%E3%80%91%E6%96%AF%E5%9D%A6%E7%BA%B3%E6%A0%91/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">上一篇</strong>
      <div class="article-nav-title">
        
          【状压DP】斯坦纳树.md
        
      </div>
    </a>
  
  
    <a href="/1111/11/11/%E3%80%90%E7%BA%BF%E5%BD%A2DP%E7%BB%83%E4%B9%A0%E3%80%91%E6%B4%9B%E8%B0%B7%20P1868%E9%A5%A5%E9%A5%BF%E7%9A%84%E5%A5%B6%E7%89%9B%20P1091%E5%90%88%E5%94%B1%E9%98%9F%E5%BD%A2%20P1541%E4%B9%8C%E9%BE%9F%E6%A3%8B%20P1020%E5%AF%BC%E5%BC%B9%E6%8B%A6%E6%88%AA/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">下一篇</strong>
      <div class="article-nav-title">【线形DP练习】洛谷 P1868饥饿的奶牛 P1091合唱队形 P1541乌龟棋 P1020导弹拦截.md</div>
    </a>
  
</nav>

  
</article>



</section>
        
          <aside id="sidebar">
  
    <div class="widget-wrap">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <h1 class="blog-title">蓝湖畔淅淅沥沥的雨</h1>
    <h2 class="blog-subtitle">All tragedy erased, I see only wonders...</h2>
    <ul class="blog-link">
     
          <a href="/" title="Home">
            <li>主页</li>
          </a>
        
          <a href="/archives" title="Archives">
            <li>归档</li>
          </a>
        
          <a href="/categories" title="Categories">
            <li>分类</li>
          </a>
        
          <a href="/tags" title="Tags">
            <li>标签</li>
          </a>
        
          <a href="/knightabout" title="Knightabout">
            <li>关于</li>
          </a>
        
          <a href="/bridges" title="Bridges">
            <li>传送门</li>
          </a>
        
          <a href="/announcement" title="Announcement">
            <li>公告</li>
          </a>
        
    </ul>
  </div>
</div>

  
    <div class="widget-wrap">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <img class="avatar" src="/images/avatar.png">
    <h2 class="author">StarsWhisper</h2>
    <h3 class="description"></h3>
    <div class="count-box">
      <a href="/archives"><div><strong>75</strong><br>文章</div></a>
      <a href="/categories"><div><strong>31</strong><br>分类</div></a>
      <a href="/tags"><div><strong>56</strong><br>标签</div></a>
    </div>



    <div class="social-link">
      
        <a class="hvr-bounce-in" href="https://github.com/Wldcmzy" target="_blank" title="Github">
          Github
        </a>
      
        <a class="hvr-bounce-in" href="https://blog.csdn.net/wldcmzy" target="_blank" title="CSDN">
          CSDN
        </a>
      
        <a class="hvr-bounce-in" href="https://space.bilibili.com/83743701" target="_blank" title="bilibili(无技术和学习内容)">
          bilibili(无技术和学习内容)
        </a>
      
    </div>

    <div class="friend-link">
      <h2>友情链接</h2>
      
        <a class="hvr-bounce-in" href="https://shanamaid.github.io/" target="_blank" title="夏娜主题作者的博客">
          夏娜主题作者的博客
        </a>
      
    </div>
  </div>
</div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy;2021 - 2022 StarsWhisper<br>
      由<a href="http://hexo.io/" target="_blank">Hexo</a>强力驱动 | 
      主题-<a target="_blank" rel="noopener" href="https://github.com/ShanaMaid/hexo-theme-shana">Shana</a>(但是魔改)
      
    </div>
    
  </div>
</footer>
    </div>
    

<script src="//apps.bdimg.com/libs/jquery/2.1.4/jquery.min.js"></script>
<script src="//apps.bdimg.com/libs/wow/0.1.6/wow.min.js"></script>
<script>
new WOW().init();
</script>   


  
<link rel="stylesheet" href="/plugin/fancybox/jquery.fancybox.css">

  
<script src="/plugin/fancybox/jquery.fancybox.pack.js"></script>




  
<link rel="stylesheet" href="/plugin/galmenu/GalMenu.css">

  
<script src="/plugin/galmenu/GalMenu.js"></script>

  <div class="GalMenu GalDropDown">
      <div class="circle" id="gal">
        <div class="ring">
          
            <a href="/announcement" title="" class="menuItem">公告</a>
          
            <a href="/tags" title="" class="menuItem">标签</a>
          
            <a href="/categories" title="" class="menuItem">分类</a>
          
            <a href="/archives" title="" class="menuItem">归档</a>
          
            <a href="/knightabout" title="" class="menuItem">关于</a>
          
            <a href="/bridges" title="" class="menuItem">传送门</a>
          
        </div>
        
          <audio id="audio" src="#"></audio>
        
      </div> 
</div>
<div id="overlay" style="opacity: 1; cursor: pointer;"></div>
  <script type="text/javascript">var items = document.querySelectorAll('.menuItem');
    for (var i = 0,
    l = items.length; i < l; i++) {
      items[i].style.left = (50 - 35 * Math.cos( - 0.5 * Math.PI - 2 * (1 / l) * i * Math.PI)).toFixed(4) + "%";
      items[i].style.top = (50 + 35 * Math.sin( - 0.5 * Math.PI - 2 * (1 / l) * i * Math.PI)).toFixed(4) + "%"
    }</script>
<script type="text/javascript">
  $(document).ready(function() {
    $('body').GalMenu({
      'menu': 'GalDropDown'
    })
  });
</script>

  <section class="hidden-xs"> 
  <ul class="cb-slideshow"> 
    <li><span>苟利</span></li> 
    <li><span>国家</span></li> 
    <li><span>生死以</span></li> 
    <li><span>岂能</span></li> 
    <li><span>祸福</span></li> 
    <li><span>趋避之</span></li> 
  </ul>
</section>

<script src="/js/script.js"></script>




  </div>
</body>
</html>